#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
long long n,m,sum,ans;
char st[2010];
bool cmp=true;
struct cxk
{
	char c;
	long long add;
	long long del;
}a[30],b[1000];
int main()
{
	freopen("hw.in","r",stdin);
	freopen("hw.out","w",stdout);
	scanf("%lld%lld",&m,&n);
	scanf("%s",&st);
	for(int i=1;i<=m;i++)
	{
		a[1].c=getchar();
		scanf("%c%lld%lld",&a[i].c,&a[i].add,&a[i].del);
		if(a[i].add!=a[i].del)
		{
			cmp=false;
		}
		b[int(a[i].c)]=a[i];
	}
	if(n==2)
	{
		if(st[0]!=st[1])
		{
			printf("%lld",min(a[1].del,min(a[2].del,min(a[1].add,a[2].add))));
		}
		if(st[0]==st[1])
		{
			printf("0");
		}
		return 0;
	}
	else if(n==3&&cmp==true)
	{
		 if(st[0]==st[2]&&st[2]==st[1])
		 {
		 	printf("0");
		 	return 0;
		 }
		 else if(st[0]==st[2]&&st[2]!=st[1])
		 {
		 	printf("0");
		 	return 0;
		 }
		 else if(st[1]==st[2]&&st[1]!=st[0])
		 {
		 	sum=min(b[int(st[1])].del,b[int(st[0])].del);
		 	ans=min(b[int(st[1])].add*2,b[int(st[0])].add);
		 	printf("%lld",min(ans,sum));
		 }
		 else if(st[1]==st[0]&&st[2]!=st[1])
		 {
		 	sum=min(b[int(st[1])].del,b[int(st[2])].del);
		 	ans=min(b[int(st[1])].add*2,b[int(st[2])].add);
		 	printf("%lld",min(ans,sum));
		 }
		 else if(st[1]!=st[0]&&st[0]!=st[2]&&st[1]!=st[2])
		 {
		 	sum=min(b[int(st[1])].add+b[int(st[2])].add,b[int(st[1])].add+b[int(st[0])].add);
		 	ans=min(b[int(st[1])].del+b[int(st[0])].del,b[int(st[0])].del+b[int(st[2])].del);
		 	ans=min(ans,b[int(st[1])].del+b[int(st[2])].del);
		 	printf("%lld",min(ans,sum));
		 }
	} 
	else if(n==3&&cmp==false)
	{
		if(st[0]==st[2]&&st[2]==st[1])
		 {
		 	printf("0");
		 	return 0;
		 }
		 else if(st[0]==st[2]&&st[2]!=st[1])
		 {
		 	 printf("0");
		 	 return 0;
		 }
		 else if(st[1]==st[2]&&st[1]!=st[0])
		 {
			 sum=min(b[int(st[1])].del,b[int(st[0])].del);
			 ans=min(b[int(st[1])].add*2,b[int(st[0])].add);
			 printf("%lld",min(ans,sum));
		 }
		 else if(st[1]==st[0]&&st[2]!=st[1])
		 {
			 sum=min(b[int(st[1])].del,b[int(st[2])].del);
			 ans=min(b[int(st[1])].add*2,b[int(st[2])].add);
			 printf("%lld",min(ans,sum));
		 }
		 else if(st[1]!=st[0]&&st[0]!=st[2]&&st[1]!=st[2])
		 {
			 sum=min(b[int(st[1])].add+b[int(st[2])].add,b[int(st[1])].add+b[int(st[0])].add);
			 ans=min(b[int(st[1])].del+b[int(st[0])].del,b[int(st[0])].del+b[int(st[2])].del);
			 ans=min(ans,b[int(st[1])].del+b[int(st[2])].del);
		     printf("%lld",min(ans,sum));
		 } 
	}
	else
	{
		sum=0;
		printf("%lld",sum);
		return 0;
	}
	return 0;
}
